
def spacify(input, dict):
    """Given a string and a dictionary, if it is possible to seperate the string
    into a set of words that are in the dictionary, returns a string equivilant to
    the input string but with spaces between the valid dictionary words. If there
    is no way to break up the input string into a set of dictionary words, returns 
    None."""

    if len(input) == 0:
        return input

    first_n_spacified = [None for i in range(len(input) + 1)]
    first_n_spacified[0] = "" # padding the beginning to make the following code a bit cleaner

    for i in range(1, len(input)+1):
        # fill in the ith element of first_n_spacified
        for split in range(0,i):
            left = first_n_spacified[split]
            right = input[split:i]
            if left is not None and right in dict:
                first_n_spacified[i] = left + " " + right
                break

    return str.strip(first_n_spacified[-1])

if __name__ == "__main__":
    dict = {"two","blobs","walk","down","the","road","together","eating","peanut","butter","blob","do","he","to","ether","eat","pea","nut","butt","but","butter"}
    print(spacify("twoblobswalkdowntheroadtogethereatingpeanutbutter", dict))